A random number generator (RNG) is an efficient device that transforms short random seeds into long pseudo-random strings. A classical RNG is the linear congruential generator (LCG) that is based on the recursion x.sub.i+1 =ax.sub.i +b(mod N). It is well known that the LCG passes certain statistical tests, e.g., for a clever choice of the parameters a,b,N it generates well mixed numbers (see Knuth 1980). There are more elaborate statistical tests which the LCG fails. Stern (1987) shows that the sequence generated by the LCG can be inferred even if the parameters a,b,N and the seed x.sub.0 are all unknown.
The concept of a perfect random number generator (PRNG) has been introduced by Blum, Micali (1982) and Yao (1982). A RNG is perfect if it passes all polynomial time statistical tests, i.e., the distribution of output sequences cannot be distinguished from the uniform distribution of sequences of the same length. So far, the proofs of perfectness for the known PRNG's are all based on unproven complexity assumptions. This is because superpolynomial complexity lower bounds cannot be proven.
Perfect random number generators have been established, for example, based on the discrete logarithm by Blum, Micali (1982), based on quadratic residuosity by Blum, Blum, Shub (1982), based on one way functions by Yao (1982), and based on Rivest/Shamir/Adleman (RSA) encryption and factoring by Alexi, Chor, Goldreich and Schnorr (1984). All these PRNG's are less efficient than the LCG. The RSA/RABIN-generators are the most efficient of these generators. They successively generate log N pseudo-random bits by one modular multiplication with a modulus that is N bit long.
Disclosure of the Invention
In accordance with the present invention, a random sequence generator generates a random sequence from a seed random sequence which is of substantially shorter length. Most likely, the seed would be truly random and the generated sequence would be pseudo-random, but the term "random" is used to include both random and pseudo-random sequences. The generator performs a tree operation by extending, at each node of a tree structure, a node input random sequence. A plurality of node output sequences of the tree structure together comprise a final random output sequence. The final random output sequence is preferably generated as successive leaves of the tree structure. The tree structure allows for direct access to any leaf as a starting leaf of a sequence. The parallel structure of the tree allows for generation of the sequence with parallel processors which, but for initial seeds, may operate independently of each other.
In a preferred embodiment, each node input sequence is extended by the RSA operation EQU y=a.sub.e x.sup.e +a.sub.e-1 x.sup.e-1 + . . . +a.sub.1 x+a.sub.0 (mod N)
where e, a.sub.e, a.sub.e-1, . . . , a.sub.0 and N are integers, the node input sequence represents x and the node output sequence represents y. In a preferred system, the RSA function is reduced by setting all a's equal to zero except one, a.sub.d, which is set to equal one. The greatest common divisor of d and Euler's Totient function .phi.(N) is equal to one. Specifically, N is the product of two large random primes p and q, and d is an integer that is relatively prime to (p-1) (q-1), preferably 3.
In either a sequential or a tree operation, the final sequence is generated in iterative steps. At each step, a new string of bits is obtained by applying a function to significantly less than all of the bits of a previous string. At least part of the bits of a previous string to which the function is not applied are utilized toward the output, either directly or with application of the function in a tree structure.
One application of the random sequence generator is in an encryption system. An encryption unit performs a transform between an encrypted message and a nonencrypted message using the random sequence generated by the random sequence generator. An index may be applied to the generator to indicate the leaf of the tree at which the sequence applied to the encryption unit begins.